동형암호와 영지식 증명의 융합

1. 서론

클라우드 컴퓨팅과 데이터 아웃소싱의 보편화는 현대 디지털 경제의 핵심 동력이 되었으나, 이는 데이터의 **기밀성(Confidentiality)**과 위탁된 연산 결과의 **무결성(Integrity)**을 동시에 보장해야 하는 근본적인 과제를 제기한다.1 전통적인 암호 기술은 저장되거나(data-at-rest) 전송 중인(data-in-transit) 데이터를 효과적으로 보호하지만, 데이터 분석이나 처리를 위해서는 필연적으로 복호화 과정을 거쳐야 한다. 이 과정에서 원본 데이터, 즉 평문(plaintext)이 신뢰할 수 없는 제3자 서버에 노출될 위험이 발생하며, 이는 데이터 프라이버시의 심각한 침해로 이어질 수 있다.2

이러한 딜레마를 해결하기 위한 차세대 암호학적 패러다임으로 ’암호화된 상태에서의 검증 가능 연산(Verifiable Computation on Encrypted Data)’이 부상하고 있다.5 이 개념은 계산 능력이 상대적으로 낮은 클라이언트가 강력한 컴퓨팅 자원을 보유한 외부 서버에 연산을 위탁하되, 서버는 연산 결과와 함께 해당 연산이 ‘정확하게’ 수행되었음을 증명하는 암호학적 증거를 반환하는 모델을 지향한다.5 이를 통해 데이터 소유자는 자신의 민감한 정보를 전혀 노출하지 않으면서도, 원격지에서 수행된 계산 결과를 수학적으로 신뢰할 수 있게 된다.

이 혁신적인 패러다임은 두 가지 핵심 암호 기술의 정교한 융합을 통해 실현된다. 첫째는 **동형암호(Homomorphic Encryption, HE)**로, 데이터를 암호화된 상태 그대로 복호화 없이 직접 연산할 수 있게 하여 데이터의 기밀성을 원천적으로 보장한다.9 둘째는 **영지식 증명(Zero-Knowledge Proof, ZKP)**으로, 연산에 사용된 비밀 정보를 일절 공개하지 않으면서 연산 과정의 정당성과 결과의 무결성을 수학적으로 증명하는 역할을 수행한다.12

본 보고서는 이 두 핵심 기술의 기본 원리부터 심층적인 수학적 기반, 주요 스킴(scheme) 비교 분석을 수행한다. 나아가, 이들을 결합하여 ’검증 가능한 동형암호’를 구현할 때 발생하는 본질적인 기술적 난제들을 탐구하고, 프라이버시 보존 머신러닝, 검증 가능한 전자 투표 등 잠재적 응용 분야와 향후 전망을 심도 있게 조망하는 것을 목표로 한다.

2. 기밀성 보장을 위한 연산 암호 - 동형암호(Homomorphic Encryption)

본 장에서는 암호화된 데이터에 대한 연산을 가능하게 하여 데이터 기밀성을 보장하는 동형암호의 기본 원리, 발전 과정, 수학적 기반 및 주요 스킴들을 심층적으로 분석한다.

2.1 동형암호의 원리 및 발전 과정

동형암호는 평문(plaintext)에 대한 연산 결과가 암호문(ciphertext)에 대한 연산 결과와 동일한 구조를 유지하도록 하는 암호화 기법이다.10 수학적으로, 평문 공간을 (P, \otimes), 암호문 공간을 (C, \oplus)라 할 때, 암호화 함수 E와 복호화 함수 D에 대해 다음의 준동형사상(homomorphism) 관계가 성립한다.15

D(E(m_1) \oplus E(m_2)) = m_1 \otimes m_2

이는 두 개의 암호문 E(m_1)과 E(m_2)를 복호화하지 않고 연산자 \oplus로 연산한 뒤 그 결과를 복호화하면, 원래의 평문 m_1과 m_2를 연산자 \otimes로 연산한 것과 동일한 결과를 얻음을 의미한다.9

동형암호 기술은 지원하는 연산의 종류와 횟수에 따라 다음과 같이 단계적으로 발전해왔다.11

• 부분 동형암호 (Partially Homomorphic Encryption, PHE): 덧셈 또는 곱셈 중 한 가지 종류의 연산만을 무제한으로 지원하는 암호 방식이다. 대표적인 예로 Paillier 암호는 덧셈 동형(additive homomorphism) 속성을 가지며, ElGamal 암호나 암호화되지 않은 RSA는 곱셈 동형(multiplicative homomorphism) 속성을 가진다.16 PHE는 특정 연산에 대해 매우 효율적이지만, 수행할 수 있는 계산의 종류가 매우 제한적이라는 명확한 한계를 지닌다.23
• 일부 동형암호 (Somewhat Homomorphic Encryption, SHE): 덧셈과 곱셈 연산을 모두 지원하지만, 사전에 정해진 횟수나 회로 깊이(circuit depth) 내에서만 연산이 가능한 방식이다.11 대부분의 현대 동형암호 스킴은 암호화 과정에서 보안을 위해 의도적으로 작은 오류, 즉 ’잡음(noise)’을 추가한다.11 동형 연산, 특히 곱셈 연산을 수행할 때마다 이 잡음이 점차 증폭되며, 잡음이 특정 임계치를 넘어서면 평문 메시지를 간섭하여 올바른 복호화가 불가능해진다.17 이것이 SHE가 제한된 횟수의 연산만을 지원하는 근본적인 이유이다.
• 완전 동형암호 (Fully Homomorphic Encryption, FHE): 덧셈과 곱셈 연산을 이론상 무한히 수행할 수 있는 가장 이상적인 형태의 동형암호이다.9 이는 SHE의 잡음 누적 문제를 해결하는 ’부트스트래핑(Bootstrapping)’이라는 혁신적인 기술을 통해 달성된다.11

결국 동형암호 기술 발전의 역사는 연산 과정에서 필연적으로 발생하는 ’잡음과의 싸움’이라 할 수 있다. 보안을 위해 도입된 잡음이 역설적으로 연산의 횟수를 제한하는 족쇄가 되었고, 이 문제를 어떻게 제어하고 극복하는지가 기술 발전의 핵심 과제가 되었다.

2.2 완전 동형암호를 향한 돌파구: 부트스트래핑(Bootstrapping)

부트스트래핑은 잡음이 과도하게 누적된 암호문을 ’새로 고침(refresh)’하여 잡음 수준을 초기화하는 혁신적인 절차로, SHE를 FHE로 격상시키는 핵심 기술이다.11 2009년 Craig Gentry에 의해 최초로 제안된 이 기법은 암호학계의 오랜 난제를 해결한 기념비적인 발견으로 평가받는다.11

부트스트래핑의 원리는 복호화 회로(decryption circuit) 자체를 동형적으로 평가(homomorphically evaluate)하는 데 있다.11 구체적인 과정은 다음과 같다.

1. 잡음이 임계치에 가까워진 암호문 c = E(m)이 있다.
2. 데이터 소유자는 자신의 비밀키 sk를 공개키로 암호화한 E(sk)를 서버에 제공한다.
3. 서버는 잡음이 많은 암호문 c와 암호화된 비밀키 E(sk)를 입력으로 받아, 복호화 함수 D(sk, c)를 동형적으로 계산한다.
4. 이 연산의 결과로 서버는 E(D(sk, c)) = E(m)과 동일한 의미를 갖는 새로운 암호문 c'을 얻는다.
5. 이 새로운 암호문 c'은 여전히 평문 m을 암호화하고 있지만, 연산 과정에서 생성된 새로운 잡음을 가지므로 전체 잡음 수준은 현저히 낮아진다.11

이 과정을 통해 이론적으로 어떤 깊이의 회로라도 암호화된 상태에서 계산하는 것이 가능해졌으며, 이는 완전 동형암호의 실현을 알리는 신호탄이 되었다.

2.3 현대 동형암호 스킴의 수학적 기반: LWE 문제

현대 FHE 스킴의 보안성은 대부분 격자(lattice) 위에서의 어려운 수학 문제에 기반하며, 그중에서도 LWE(Learning With Errors) 문제가 핵심적인 역할을 한다.18 격자 기반 암호는 현재까지 알려진 가장 강력한 공격 방법인 양자 컴퓨터의 쇼어 알고리즘(Shor’s algorithm)에도 안전한 것으로 알려져, 양자내성암호(Post-Quantum Cryptography, PQC)의 유력한 후보로 간주된다.18

LWE 문제는 비밀 벡터 \vec{s} \in \mathbb{Z}_q^n에 대해, (\vec{a}_i, b_i = \langle \vec{a}_i, \vec{s} \rangle + e_i) \pmod{q} 형태의 수많은 샘플이 주어졌을 때, 비밀 벡터 \vec{s}를 찾는 것이 계산적으로 매우 어렵다는 문제이다. 여기서 \vec{a}_i는 랜덤 벡터이고, e_i는 특정 분포(예: 가우시안 분포)에서 추출된 작은 크기의 오류(잡음) 항이다.25 만약 잡음 e_i가 없다면 이 문제는 가우스 소거법으로 쉽게 풀 수 있지만, 잡음의 존재가 문제를 어렵게 만든다.

LWE 문제를 이용한 기본적인 암호화 및 복호화 과정은 다음과 같다.30

• 암호화 Enc(\vec{s}, m): 한 비트 메시지 m \in \{0, 1\}을 암호화하기 위해, 먼저 LWE 샘플 (\vec{a}, b = \langle \vec{a}, \vec{s} \rangle + e)를 생성한다. 그 후, 메시지를 인코딩하여 b에 더해 암호문 c = (\vec{a}, b' = b + m \cdot \lfloor q/2 \rfloor)를 생성한다.
• 복호화 Dec(\vec{s}, c): 암호문 c = (\vec{a}, b')를 복호화하기 위해 b' - \langle \vec{a}, \vec{s} \rangle를 계산한다. 이 결과는 (m \cdot \lfloor q/2 \rfloor + e) \pmod{q}에 가까운 값이 된다. 이 값이 \lfloor q/2 \rfloor에 가까우면 m=1로, 0에 가까우면 m=0으로 판별하여 원본 메시지를 복원한다.

실제 FHE 스킴에서는 효율성을 위해 LWE 문제의 변형인 RLWE(Ring-LWE) 문제가 널리 사용된다.15 RLWE는 LWE의 벡터 연산을 다항식 환(polynomial ring), 예컨대

\mathbb{Z}_q[X]/(X^N+1)에서의 연산으로 대체한 것이다. 이를 통해 키 크기를 \mathcal{O}(n^2)에서 \mathcal{O}(n)으로 줄이고, NTT(Number Theoretic Transform)라는 고속 푸리에 변환과 유사한 알고리즘을 사용하여 다항식 곱셈을 \mathcal{O}(N \log N)의 시간 복잡도로 매우 효율적으로 수행할 수 있다.32 BFV, CKKS와 같은 대부분의 2세대 이후 FHE 스킴은 이 RLWE 문제를 기반으로 설계되었다.29

2.4 주요 동형암호 스킴 심층 비교: BFV vs. CKKS

현대 동형암호 라이브러리에서 가장 널리 사용되는 두 스킴은 BFV와 CKKS이며, 이 둘은 동일한 RLWE 기반 위에 있으면서도 잡음을 다루는 방식과 지원하는 연산의 종류에서 근본적인 차이를 보인다.

• BFV/BGV 스킴 (정확한 연산): Fan과 Vercauteren이 제안한 BFV 스킴(그리고 유사한 구조의 BGV 스킴)은 정수(integer) 또는 고정소수점(fixed-point) 수에 대한 정확한(exact) 산술 연산을 지원한다.25
• 잡음 처리: BFV에서 잡음은 암호문 값의 최하위 비트(LSB) 영역에 존재한다. 복호화 과정에서는 특정 임계값보다 작은 잡음을 완전히 제거하여 오차 없는 평문 값을 복원한다.26 곱셈 연산 시 잡음이 크게 증폭되므로, 깊은 연산을 위해서는 부트스트래핑이 필수적이다.35
• 주요 용도: 결과의 정확성이 반드시 보장되어야 하는 금융 계산, 통계 연산, 데이터베이스 쿼리, 유전체 분석 등에 적합하다.
• CKKS 스킴 (근사 연산): Cheon, Kim, Kim, Song이 제안한 CKKS 스킴은 실수(real number) 및 복소수(complex number)에 대한 근사(approximate) 산술 연산을 효율적으로 지원하도록 설계되었다.31
• 잡음 처리: CKKS에서는 잡음이 값의 일부로 취급되며, 복호화 후에도 제거되지 않는다. 대신, 연산 과정에서 ’리-스케일링(re-scaling)’이라는 기법을 통해 잡음의 크기를 평문과 비슷한 수준으로 유지하며 관리한다.35 이로 인해 연산 결과는 항상 약간의 오차를 포함하는 근사값이 된다.31 특히 곱셈 시 잡음 증가가 지수적이 아닌 선형적이어서, 부트스트래핑 없이도 상대적으로 깊은 회로를 효율적으로 계산할 수 있다.35
• 주요 용도: 머신러닝 모델 추론, 신호 처리, 과학 계산 등 일정 수준의 정밀도 손실을 허용할 수 있는 실수 연산이 필요한 분야에서 매우 강력한 성능을 보인다.36

BFV와 CKKS의 분화는 ’정확성’과 ‘효율성’ 사이의 근본적인 트레이드오프를 명확히 보여준다. 하나의 동형암호 스킴이 모든 응용 분야에 최적인 것은 아니며, 해결하고자 하는 문제의 특성에 따라 적합한 스킴을 선택하는 것이 매우 중요하다. 1원의 오차도 허용되지 않는 금융 거래에는 BFV가 필수적이지만, 수백만 개의 파라미터를 가진 AI 모델 추론에서는 약간의 정밀도 손실이 최종 결과에 큰 영향을 미치지 않으므로 CKKS가 압도적으로 유리하다.

3. 무결성 증명을 위한 암호학적 도구 - 영지식 증명(Zero-Knowledge Proof)

본 장에서는 연산의 결과가 올바르다는 것을 비밀 정보 노출 없이 증명하는 영지식 증명의 기본 속성과, 현재 가장 널리 사용되는 두 시스템인 zk-SNARKs와 zk-STARKs를 비교 분석한다.

3.1 영지식 증명의 핵심 속성

영지식 증명(ZKP)은 증명자(Prover)가 검증자(Verifier)에게 어떤 명제가 참이라는 사실을, 그 명제가 참이라는 사실 외에는 어떠한 추가 정보도 노출하지 않고 납득시키는 암호학적 프로토콜이다.14 이는 ’무엇을 알고 있는지’는 철저히 숨긴 채, ‘알고 있다는 사실’ 자체만을 증명하는 기술이다.12

모든 영지식 증명 시스템은 다음 세 가지 핵심적인 원칙을 반드시 만족해야 한다.13

1. 완전성 (Completeness): 증명자가 증명하려는 명제가 실제로 참일 경우, 정직한 증명자는 프로토콜을 정상적으로 따르면 항상 정직한 검증자를 납득시킬 수 있어야 한다.
2. 건전성 (Soundness): 증명자가 증명하려는 명제가 거짓일 경우, 악의적인 증명자가 어떤 속임수를 쓰더라도 정직한 검증자를 속여서 명제가 참이라고 믿게 만들 수 없어야 한다 (무시할 수 있을 만큼 낮은 확률로).
3. 영지식성 (Zero-Knowledge): 명제가 참이어서 증명에 성공하더라도, 검증자는 ’해당 명제가 참이다’라는 단 하나의 정보 외에는 증명자가 가진 비밀 정보(witness)에 대해 그 어떤 것도 알 수 없어야 한다.

ZKP는 증명자와 검증자 간의 상호작용 방식에 따라 **대화형(Interactive)**과 **비대화형(Non-Interactive)**으로 구분된다.13 대화형 ZKP는 증명자와 검증자가 여러 차례 질의-응답(challenge-response)을 주고받으며 증명을 완성하는 반면, 비대화형 ZKP는 증명자가 생성한 단 하나의 메시지(증명)만으로 검증이 완료된다. 블록체인과 같이 참여자들이 동시에 온라인 상태임을 보장할 수 없는 비동기적 환경에서는 비대화형 ZKP가 필수적으로 요구된다.

3.2 주요 영지식 증명 시스템 비교: zk-SNARKs vs. zk-STARKs

비대화형 ZKP 중에서 현재 가장 주목받는 두 기술은 zk-SNARKs와 zk-STARKs이다.

• zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge): 간결하고(Succinct) 비대화형인(Non-interactive) 지식 논증을 의미한다.43
• 간결성(Succinct): zk-SNARKs의 가장 큰 특징은 증명의 크기가 매우 작고(수백 바이트 수준) 검증에 소요되는 시간이 매우 빠르다는 점이다.42 이는 증명을 블록체인과 같은 공개 원장에 기록할 때 발생하는 저장 및 계산 비용을 최소화해주므로 매우 중요한 장점이다.47
• 신뢰 설정(Trusted Setup): Groth16과 같은 대부분의 효율적인 zk-SNARKs는 시스템 초기에 ’공통 참조 문자열(Common Reference String, CRS)’이라는 공개 파라미터를 생성하기 위한 신뢰 설정 과정이 필요하다.43 이 과정에서 생성되고 폐기되어야 하는 비밀값, 일명 “독성 폐기물(toxic waste)“이 만약 유출된다면, 시스템 전체의 보안이 무너지며 누구든 위조된 증명을 생성할 수 있는 심각한 위험이 존재한다.48
• 양자 저항성: 보안성이 타원곡선 암호(ECC)의 이산 로그 문제와 같은 수학적 난제에 기반하는 경우가 많아, 양자 컴퓨터가 개발되면 보안이 깨질 수 있다.44
• zk-STARKs (Zero-Knowledge Scalable Transparent Argument of Knowledge): 확장 가능하고(Scalable) 투명한(Transparent) 지식 논증을 의미한다.43
• 투명성(Transparent): zk-STARKs의 가장 큰 장점은 신뢰 설정 과정이 전혀 필요 없다는 것이다.47 공개적으로 검증 가능한 무작위성을 사용하므로 특정 그룹에 대한 신뢰 가정이 제거되어 탈중앙화 시스템에 더 적합하다.44
• 확장성(Scalable): 증명해야 할 계산의 복잡도가 증가하더라도, 증명 생성 시간과 검증 시간이 준선형적(quasilinear)으로 증가한다. 이는 매우 큰 규모의 계산에 대해서는 zk-SNARKs보다 더 효율적일 수 있음을 의미한다.47
• 증명 크기: zk-SNARKs에 비해 증명의 크기가 수십 킬로바이트 이상으로 훨씬 크다는 단점이 있다.48 이는 저장 및 전송 비용을 증가시키는 요인이다.
• 양자 저항성: 보안성이 충돌 저항성 해시 함수(Collision-Resistant Hash Functions)에 기반하므로, 현재 알려진 양자 컴퓨터 공격에 강한 것으로 평가된다.48

ZKP 기술의 발전은 ’신뢰’와 ‘성능’ 사이의 트레이드오프를 최적화하는 과정으로 볼 수 있다. zk-SNARKs는 증명 크기와 검증 속도라는 압도적인 성능을 달성하기 위해 ’신뢰 설정’이라는 중앙화된 신뢰 가정을 도입했다. 반면 zk-STARKs는 이 신뢰 가정을 제거하여 완전한 투명성을 확보하는 대신, 증명 크기가 커지는 성능적 대가를 치렀다. 따라서 어떤 ZKP 시스템을 선택할 것인지는 단순히 기술적 우위를 넘어, 시스템이 추구하는 철학(예: 탈중앙화)과 현실적 제약(예: 온체인 비용) 사이의 균형을 맞추는 문제이다.

더 나아가, ZKP는 단순한 프라이버시 기술을 넘어 ’계산 압축(Computation Compression)’을 통한 확장성 솔루션으로서 더 큰 파급력을 가진다. 복잡하고 긴 계산을 수행한 후, 그 결과가 올바르다는 것을 매우 작고 빠르게 검증 가능한 ’증명’으로 압축할 수 있는 능력은 블록체인 확장성 문제의 핵심 해결책인 ZK-Rollups의 기반이 된다.45 이는 ZKP가 프라이버시 코인을 넘어, 블록체인 플랫폼의 성능 한계를 돌파하는 핵심 인프라 기술로 자리매김하고 있음을 시사한다.

4. 기밀성과 무결성의 융합 - 검증 가능한 동형암호(Verifiable Homomorphic Encryption)

본 장에서는 동형암호와 영지식 증명을 결합하여 데이터의 기밀성과 연산의 무결성을 동시에 달성하는 ’검증 가능한 동형암호’의 필요성, 프로토콜 설계, 그리고 구현 시 발생하는 핵심적인 기술적 난제들을 분석한다.

4.1 동형암호의 내재적 한계와 검증의 필요성

동형암호는 암호문 c = E(m)에 대한 연산 f의 결과로 c' = Eval(f, c)를 제공하지만, 이 결과 암호문 c'이 정말로 함수 f를 올바르게 적용한 결과인지는 보장하지 않는다.7 악의적이거나 버그가 있는 서버는 약속된 함수 f 대신 다른 함수 g를 적용하여 c'' = Eval(g, c)를 반환할 수 있으며, 사용자는 결과를 복호화하여 의미 없는 값을 얻기 전까지 이러한 조작을 탐지할 방법이 없다.32

이러한 문제는 동형암호가 정의상 **가단성(Malleability)**을 갖기 때문에 발생한다. 가단성이란 하나의 암호문으로부터 관련된 다른 유효한 암호문을 생성할 수 있는 성질로, 동형 연산을 가능하게 하는 핵심 속성이지만 동시에 무결성 측면에서는 취약점으로 작용한다.11

결국 동형암호(HE)는 데이터의 기밀성은 완벽하게 보장하지만 연산의 무결성은 보장하지 못한다. 반대로, 영지식 증명(ZKP)은 연산의 무결성은 증명할 수 있지만, 증명을 생성하는 주체(Prover)가 원본 데이터(witness)에 직접 접근해야 하므로 데이터의 기밀성이 깨지는 문제가 발생한다.7 따라서 신뢰할 수 없는 환경에서 데이터의 기밀성과 연산의 무결성을 모두 보장하기 위해서는 이 두 기술의 결합이 필수적이다.

4.2 프로토콜 설계: 동형암호와 영지식 증명의 결합 (zkFHE)

검증 가능한 동형암호, 또는 zkFHE 프로토콜은 동형암호의 기밀성 보장 능력과 영지식 증명의 무결성 증명 능력을 결합한 것이다. 전체적인 워크플로우는 다음과 같이 설계될 수 있다.57

1. 암호화 (Encryption): 사용자는 자신의 데이터 m을 FHE 공개키 pk로 암호화하여 암호문 c = E_{pk}(m)을 생성하고, 이를 연산을 위탁할 서버(Prover)에게 전송한다.
2. 동형 연산 및 증명 생성 (Homomorphic Evaluation & Proof Generation): 서버는 전달받은 암호문 c와 사전에 약속된 함수 f에 대해 동형 연산을 수행하여 결과 암호문 c' = Eval(f, c)를 계산한다. 이와 동시에, 이 계산 과정이 FHE 스킴의 규칙에 따라 정직하게 수행되었음을 증명하는 영지식 증명 \pi를 생성한다.
3. 검증 (Verification): 서버는 계산된 결과 암호문 c'과 무결성 증명 \pi를 사용자(Verifier)에게 반환한다. 사용자는 공개된 정보(c, f, c')를 이용하여 증명 \pi를 검증한다. 이 검증을 통해 사용자는 c'이 f(m)의 올바른 암호문임을 수학적으로 확신할 수 있다.
4. 복호화 (Decryption): 증명 검증이 성공적으로 완료되면, 사용자는 자신의 비밀키 sk를 사용하여 c'을 복호화하고 최종 결과 m' = D_{sk}(c') = f(m)을 안전하게 얻는다.

이 프로토콜에서 ZKP가 증명하는 핵심 명제는 “나는 입력 암호문 c와 함수 f를 가지고, FHE 스킴의 규칙에 따라 올바르게 동형 연산을 수행하여 출력 암호문 c'을 얻었음을 안다“는 것이다.32

4.3 기술적 도전 과제 및 해결 방안

검증 가능한 동형암호를 실제로 구현하는 데에는 여러 가지 근본적인 기술적 난제가 존재한다.32

• 근본적인 대수 구조의 불일치: 가장 큰 난제는 FHE와 ZKP가 기반하는 수학적 구조가 다르다는 점이다. 대부분의 현대 FHE 스킴은 다항식 환(polynomial ring), 즉 \mathbb{R}_q = \mathbb{Z}_q[X]/(X^N+1) 위에서 연산하는 반면, 효율적인 ZKP 시스템(특히 zk-SNARKs)은 거대한 소수 필드 \mathbb{F}_p 위에서 연산한다. 이 두 구조는 직접적으로 호환되지 않으므로, ZKP 회로 내에서 FHE의 링 연산을 ’에뮬레이션’해야 한다. 이는 마치 서로 다른 아키텍처의 CPU 명령어를 소프트웨어로 번역하는 것과 같아 엄청난 성능 저하를 유발한다.32
• FHE 유지보수 연산 증명의 복잡성: 현대 FHE 스킴은 단순 덧셈, 곱셈 외에도 잡음 관리를 위해 리-스케일링, 모듈러스 스위칭(modulus switching), 키 스위칭(key-switching) 등 복잡한 ‘유지보수’ 연산을 수행한다.35 이러한 연산들은 반올림, 기저 변환 등 ZKP의 산술 회로로 표현하기 매우 어렵고 비효율적인 비-산술적 로직을 포함하고 있어 증명 생성을 극도로 복잡하게 만든다.32
• 막대한 성능 오버헤드: FHE 연산 자체도 평문 연산에 비해 수천 배 이상 느린데 2, 이 무거운 연산 과정을 다시 ZKP 회로로 변환하고 증명을 생성하는 것은 훨씬 더 큰 계산 비용을 요구한다. 일부 연구에 따르면 ZKP 증명 생성은 네이티브 연산보다 약 1,000배에서 100,000배 더 비쌀 수 있다.7 또한, FHE 암호문은 평문보다 수백에서 수천 배 크기 때문에 19, 이 거대한 데이터를 ZKP 회로의 입력으로 사용하는 것 자체가 시스템의 복잡도를 기하급수적으로 증가시킨다.

이러한 문제들은 Verifiable HE의 실용화를 가로막는 가장 큰 장벽이다. 이 난제들을 해결하기 위한 접근 방식은 FHE 연산을 ZKP 회로로 효율적으로 ’컴파일’하는 기술의 발전에 달려있다. 이는 단순히 두 암호 기술을 결합하는 것을 넘어, FHE의 특정 연산(예: NTT, 모듈러스 스위칭)을 효율적으로 증명할 수 있는 ‘FHE 친화적인’ ZKP 시스템을 개발하거나, 반대로 ZKP로 증명하기 쉬운 구조를 가진 새로운 FHE 스킴을 설계하는 ‘공동 설계(co-design)’ 접근법을 요구한다. 이는 암호학적 프리미티브 설계와 컴파일러 최적화 기술이 융합되는 새로운 연구 분야의 등장을 예고한다.

궁극적으로 Verifiable HE는 ‘신뢰의 위임’ 모델을 근본적으로 변화시킨다. 기존 클라우드 모델에서는 사용자가 서버를 신뢰하거나(데이터 노출 감수), 신뢰하지 않는 대신 모든 연산을 로컬에서 수행해야 했다. 동형암호는 ’연산’의 위임을 가능하게 했지만 ’결과의 신뢰’는 보장하지 못했다. Verifiable HE는 ’연산’과 ’정직성에 대한 증명’을 모두 위임하면서도, 사용자는 오직 수학적 원리만을 신뢰하면 되는 새로운 모델을 완성한다.57 이는 ’신뢰할 수 있는 제3자(Trusted Third Party)’의 필요성을 제거하고, 진정한 의미의 탈중앙화된 컴퓨팅 서비스를 가능하게 하는 핵심 인프라가 될 잠재력을 지닌다.

5. 활용 사례 및 향후 전망

본 장에서는 검증 가능한 동형암호 기술이 실제로 적용될 수 있는 주요 분야를 살펴보고, 현재의 기술적 한계와 미래 연구 방향을 조망한다.

5.1 주요 응용 분야

검증 가능한 동형암호는 데이터의 기밀성과 연산의 무결성이 동시에 요구되는 다양한 민감 데이터 처리 분야에서 혁신적인 솔루션을 제공할 수 있다.

• 프라이버시 보존 머신러닝 (PPML): 사용자는 자신의 민감한 데이터(예: 의료 기록, 금융 정보)를 FHE로 암호화하여 AI 서비스 제공업체에 전송한다. 제공업체는 암호화된 데이터에 대해 AI 모델 추론(예: 질병 예측, 신용 점수 평가)을 수행하고, 암호화된 결과와 함께 추론 과정이 모델에 따라 올바르게 수행되었음을 증명하는 ZKP를 반환한다. 이를 통해 사용자는 개인정보를 전혀 노출하지 않으면서도 신뢰할 수 있는 AI 분석 결과를 얻을 수 있다.9 이는 GDPR과 같은 강력한 데이터 프라이버시 규제를 준수하면서 다자간 데이터 협업을 통한 AI 모델 개발을 가능하게 한다.19
• 검증 가능한 전자 투표 (Verifiable E-Voting): 유권자의 투표 내용은 동형암호로 암호화되어 프라이버시를 보장한다. 개표 과정에서는 암호화된 모든 투표 용지를 동형적으로 합산하여 최종 득표수를 계산한다. 이때, 전체 개표 과정(각 투표가 유효하며, 합산이 정확하게 이루어졌음)에 대한 ZKP를 생성하여 공개한다. 시민, 언론 등 제3자는 이 증명을 검증함으로써 개표 결과의 무결성을 독립적으로 확인할 수 있다.40 이를 통해 유권자의 익명성을 보장하면서도 선거 결과의 투명성과 신뢰성을 확보하는 ’종단간 검증 가능성(End-to-End Verifiability)’을 달성할 수 있다.66
• 안전한 클라우드 컴퓨팅: 기업은 민감한 비즈니스 데이터를 FHE로 암호화하여 클라우드에 저장하고, 필요한 분석(예: 재무 분석, 고객 데이터 분석)을 요청한다. 클라우드 제공업체는 동형 연산을 수행하고 결과와 ZKP를 반환한다. 기업은 내부 데이터 유출이나 클라우드 제공업체에 의한 데이터 오용 걱정 없이 클라우드의 강력한 컴퓨팅 자원을 활용하고, 결과의 정확성을 수학적으로 보장받을 수 있다.1
• 블록체인 확장성 및 프라이버시: ZK-Rollup은 다수의 트랜잭션을 오프체인에서 실행하고 그 결과의 유효성을 ZKP를 통해 온체인에서 간결하게 검증하는 레이어-2 확장 솔루션이다.55 현재는 주로 평문 상태의 연산을 증명하지만, 여기에 동형암호를 결합하면 암호화된 상태의 스마트 컨트랙트(confidential smart contract) 실행을 증명하는 것이 가능해진다. 이는 블록체인 상에서 트랜잭션의 내용(금액, 참여자 등)을 완전히 숨기면서도 확장성을 확보하는, 프라이버시와 성능을 모두 극대화하는 차세대 블록체인 플랫폼 구현으로 이어질 수 있다.71

이 기술의 높은 비용을 고려할 때, 킬러 애플리케이션은 단일 사용자가 자신의 데이터를 보호하는 경우보다는, 여러 기관이 서로의 데이터를 공개하지 않고 공동으로 분석해야 하는 규제 산업에서 등장할 가능성이 높다. 예를 들어, 여러 병원이 각자의 환자 데이터를 암호화한 상태로 공유하여 연합 학습(Federated Learning)을 수행하고, 그 학습 과정과 결과 모델의 무결성을 ZKP로 검증하는 시나리오가 대표적이다. 이는 데이터 공유의 장벽을 허물어 새로운 사회적, 경제적 가치를 창출하는 핵심 동력이 될 것이다.

5.2 현재의 한계와 미래 연구 방향

검증 가능한 동형암호가 널리 채택되기까지는 해결해야 할 여러 과제가 남아있다.

• 성능 문제: 현재 기술 수준에서 Verifiable HE는 막대한 계산 오버헤드로 인해 실
• 용성이 매우 제한적이다.2 FHE 연산과 ZKP 증명 생성을 가속하기 위한 전용 하드웨어(ASIC, FPGA) 개발 및 알고리즘 최적화 연구가 필수적이다.61
• 새로운 암호학적 프리미티브 개발: 제3.3절에서 논의된 FHE와 ZKP 간의 근본적인 대수 구조 불일치를 해소하기 위해, 두 기술에 모두 친화적인 새로운 수학적 구조(예: 격자 기반 ZKP)나 공동 설계 패러다임에 대한 연구가 시급하다.32
• 표준화 및 개발 생태계: 기술의 복잡성으로 인해 개발자들의 접근성이 매우 낮다.9 Microsoft의 SEAL, IBM의 HElib 등 FHE 라이브러리와 다양한 ZKP 라이브러리가 존재하지만, 이들을 효율적으로 통합하고 표준화하려는 노력이 필요하다. 현재 ISO를 중심으로 동형암호 표준화가 진행 중이며 15, 이러한 노력은 기술의 신뢰성을 높이고 산업계 채택을 가속화할 것이다.29

6. 결론

검증 가능한 동형암호는 데이터가 사용되는 전 과정(data-in-use)에서 기밀성과 무결성을 동시에 보장하는, 암호학의 오랜 목표인 ’암호학적 성배(Holy Grail)’에 한 걸음 더 다가서는 혁신적인 기술이다. 이는 신뢰할 수 없는 외부 환경에 민감한 데이터의 연산을 위탁하면서도 데이터 주권을 완벽하게 유지할 수 있는 새로운 컴퓨팅 모델을 제시한다.

현재는 막대한 성능 문제와 기술적 복잡성이라는 높은 장벽이 존재하지만, 알고리즘, 하드웨어, 그리고 암호학적 프리미티브에 대한 지속적인 연구 개발을 통해 이러한 한계는 점차 극복될 것이다. 미래 디지털 경제에서 이 기술은 신뢰의 인프라로 자리 잡을 잠재력을 지니고 있다. 프라이버시를 침해하지 않는 인공지능, 투명하고 안전한 민주주의 시스템, 그리고 진정으로 탈중앙화된 차세대 인터넷(Web3)을 구현하는 데 있어, 검증 가능한 동형암호는 불가결한(不可或缺) 역할을 수행할 것으로 전망된다.

7. 참고 자료

1. Homomorphic Encryption for Beginners: A Practical Guide (Part 1), https://medium.com/privacy-preserving-natural-language-processing/homomorphic-encryption-for-beginners-a-practical-guide-part-1-b8f26d03a98a
2. Homomorphic Encryption - Basics, https://www.encryptionconsulting.com/introduction-to-homomorphic-encryption/
3. 14 Fully homomorphic encryption: Introduction and bootstrap- ping - Boaz Barak, https://files.boazbarak.org/crypto/lec_15_FHE.pdf
4. 클라우드 환경에서 데이터와 AI를 지켜줄 동형암호 – 잠재력, 연구 동향 - AHHA Labs, https://ahha.ai/2023/11/02/homomorphic/
5. www.archetype.fund, https://www.archetype.fund/media/verifiable-compute-scaling-trust-with-cryptography#:~:text=Verifiable%20Computation%3A%20Enables%2C%20through%20a,computation%20was%20carried%20out%20correctly.
6. Verifiable Computation on Encrypted Data - Protocol Labs Research, https://research.protocol.ai/talks/verifiable-computation-on-encrypted-data/
7. Verifiable Compute: Scaling Trust with Cryptography - Archetype Fund, https://www.archetype.fund/media/verifiable-compute-scaling-trust-with-cryptography
8. Verifiable Computation over Encrypted Data: Current Constructions and Challenges, https://www.youtube.com/watch?v=tefXN1klTJc
9. 동형암호(Homomorphic Encryption): 암호화된 상태에서의 데이터 연산 기술, https://j2doll.tistory.com/1041
10. 소개 - 암호기술의 역사 - KISA 암호이용활성화, https://seed.kisa.or.kr/kisa/intro/EgovHistory.do
11. Homomorphic encryption - Wikipedia, https://en.wikipedia.org/wiki/Homomorphic_encryption
12. www.chainalysis.com, https://www.chainalysis.com/blog/introduction-to-zero-knowledge-proofs-zkps/#:~:text=A%20zero%2Dknowledge%20proof%2C%20or,of%20interactions%20involving%20sensitive%20data.
13. Introduction to Zero-Knowledge Proofs - Chainalysis, https://www.chainalysis.com/blog/introduction-to-zero-knowledge-proofs-zkps/
14. Zero-knowledge proof - Wikipedia, https://en.wikipedia.org/wiki/Zero-knowledge_proof
15. 동형암호 - 위키백과, 우리 모두의 백과사전, https://ko.wikipedia.org/wiki/%EB%8F%99%ED%98%95%EC%95%94%ED%98%B8
16. 동형암호 (Homomorphic Encryption, HE) - 비트코기의 IT Note - 티스토리, https://itpenote.tistory.com/707
17. 동형암호(Homomorphic Encryption) - C’s Shelter - 티스토리, https://gnuhcjh.tistory.com/25
18. 동형암호(Homomorphic Encryption) - 기술사가 들려주는 ICT(정보통신기술) Report (PE.R.SON) - 티스토리, https://soncs.tistory.com/155
19. 동형암호(Homomorphic Encryption) / ① - IT신비 - 티스토리, https://shinbe.tistory.com/entry/%EB%8F%99%ED%98%95%EC%95%94%ED%98%B8Homomorphic-Encryption-%E2%91%A0
20. Types of Homomorphic Encryption - IEEE Digital Privacy, https://digitalprivacy.ieee.org/publications/topics/types-of-homomorphic-encryption/
21. Differences FHE and PHE- Wodan AI - Secure AI, https://wodan.ai/differences-fhe-and-phe/
22. All about Homomorphic Encryption for privacy-preserving model | by Sanjay Basu, PhD, https://medium.com/my-aiml/all-about-homomorphic-encryption-for-privacy-preserving-model-98abf9f97fe
23. Somewhat Homomorphic Encryption versus Fully Homomorphic Encryption? - Cryptography Stack Exchange, https://crypto.stackexchange.com/questions/39591/somewhat-homomorphic-encryption-versus-fully-homomorphic-encryption
24. 동형암호 - 위키원, http://wiki.hash.kr/index.php/%EB%8F%99%ED%98%95_%EC%95%94%ED%98%B8
25. A High-Level Technical Overview of Fully Homomorphic Encryption - Math ∩ Programming, https://www.jeremykun.com/2024/05/04/fhe-overview/
26. 완전동형암호 연산 가속 하드웨어 기술 동향, https://ettrends.etri.re.kr/ettrends/193/0905193001/001-012_%EB%B0%95%EC%84%B1%EC%B2%9C_193%ED%98%B8.pdf
27. 완전 동형 암호에서의 정밀한 맥스 풀링 연산 - Korea Science, https://koreascience.kr/article/JAKO202319440350167.pdf
28. Recent advances of privacy-preserving machine learning based on (Fully) Homomorphic Encryption | Security and Safety (S&S), https://sands.edpsciences.org/articles/sands/full_html/2025/01/sands20240021/sands20240021.html
29. Introduction - Homomorphic Encryption Standardization, https://homomorphicencryption.org/introduction/
30. LWE와 완전동형암호에 대한 분석 및 동향 -Review of KIISC | Korea …, https://www.koreascience.kr/article/JAKO202032254872932.page
31. CKKS explained, Part 3: Encryption and Decryption – OpenMined, https://openmined.org/blog/ckks-explained-part-3-encryption-and-decryption/
32. Verifiable Fully Homomorphic Encryption, https://arxiv.org/pdf/2301.07041
33. FHE Project comparison - MVP Workshop, https://mvpworkshop.co/fhe-project-comparison/
34. Describe how the floating point Homomorphic Encryption actually works ? | by Jahanzeb, https://medium.com/@jahanxb/describe-how-the-floating-point-homomorphic-encryption-actually-works-afeaa14e1649
35. CKKS Homomorphic Encryption Part 1 - The Original Scheme - MIT, https://www.mit.edu/~linust/files/CKKS_Homomorphic_Encryption_Part_1.pdf
36. 차세대 암호 - 동형암호 - KISA 암호이용활성화, https://seed.kisa.or.kr/kisa/ngc/pec.do
37. Comparison of partial homomorphic encryption schemes - ResearchGate, https://www.researchgate.net/figure/Comparison-of-partial-homomorphic-encryption-schemes_tbl1_360370944
38. 영지식 증명 이해하기 - Tariz - Medium, https://hyun-jeong.medium.com/h-3c3d45861ced
39. 영지식 증명 - 위키백과, 우리 모두의 백과사전, https://ko.wikipedia.org/wiki/%EC%98%81%EC%A7%80%EC%8B%9D_%EC%A6%9D%EB%AA%85
40. Zero-Knowledge Proofs: A Beginner’s Guide - Dock Labs, https://www.dock.io/post/zero-knowledge-proofs
41. 초보자를 위한 영지식 증명. 소개 | by CoinEasy - Medium, https://medium.com/@coineasy/%EC%B4%88%EB%B3%B4%EC%9E%90%EB%A5%BC-%EC%9C%84%ED%95%9C-%EC%98%81%EC%A7%80%EC%8B%9D-%EC%A6%9D%EB%AA%85-e91b7dd2e802
42. [ZK 영지식 증명] 대화형과 비대화형_블록체인 냉장고 파먹기 | by Karinnovation | CURG, https://medium.com/curg/zk-%EC%98%81%EC%A7%80%EC%8B%9D-%EC%A6%9D%EB%AA%85-%EB%8C%80%ED%99%94%ED%98%95%EA%B3%BC-%EB%B9%84%EB%8C%80%ED%99%94%ED%98%95-e803745fe49b
43. ZK-SNARK 대 ZK-STARK: ZK-Proofs는 어떻게 다릅니까? - Metaverse Post, https://mpost.io/ko/zk-snarks-vs-zk-starks-how-do-zk-proofs-differ/
44. zk-SNARKs vs zk-STARKs — Comparing Zero-knowledge Proofs - Panther Protocol, https://blog.pantherprotocol.io/zk-snarks-vs-zk-starks-differences-in-zero-knowledge-technologies/
45. zk-SNARK와 zk-STARK 설명 - 고팍스 아카데미, https://academy.gopax.co.kr/zk-snarks-seolmyeong/
46. zk-STARK vs zk-SNARK : An In-Depth Comparative Analysis, https://www.quillaudits.com/blog/ethereum/zk-starks-vs-zk-snarks
47. Throne of ZK: SNARK vs. STARK, https://xangle.io/research/detail/1126
48. Comparing ZK-SNARKs & ZK-STARKs: Key Distinctions In Blockchain Privacy Protocols, https://hacken.io/discover/zk-snark-vs-zk-stark/
49. Full Guide to Understanding zk-SNARKs and zk-STARKS - Cyfrin, https://www.cyfrin.io/blog/a-full-comparison-what-are-zk-snarks-and-zk-starks
50. zk-SNARK vs zkSTARK - Explained Simple - Chainlink, https://chain.link/education-hub/zk-snarks-vs-zk-starks
51. zk-SNARKs - Tari Labs University, https://tlu.tarilabs.com/cryptography/zk-snarks
52. Trust Setup Party의 성격으로 본 zk-SNARKs의 여러가지 버전들 | by 김인근 - Medium, https://medium.com/curg/trust-setup-party%EC%9D%98-%EC%84%B1%EA%B2%A9%EC%9C%BC%EB%A1%9C-%EB%B3%B8-zk-snarks%EC%9D%98-%EC%97%AC%EB%9F%AC%EA%B0%80%EC%A7%80-%EB%B2%84%EC%A0%84%EB%93%A4-7423e4a72dd7
53. Throne of ZK: SNARK vs. STARK - Medium, https://medium.com/nonce-classic/throne-of-zk-snark-vs-stark-a7ff305a2d30
54. 17. [Session2] 영지식 증명 이해와 블록체인 활용(한양대학교-오현옥 교수) - YouTube, https://www.youtube.com/watch?v=9AQqbji7h8g
55. What Are ZK Rollups? Scalability and Privacy in Blockchain, https://www.identity.com/what-are-zk-rollups-scalability-and-privacy-in-blockchain/
56. ZK Rollups Solutions for Blockchain Scaling| Boost Performance Now - Rapid Innovation, https://www.rapidinnovation.io/post/zk-rollup-scaling-solutions-a-comprehensive-guide
57. ZK Snark and FHE Integration | Documentation - Airchains, https://docs.airchains.io/concepts/intro-to-zkfhe/zk-snark-and-fhe-integration
58. Is ZK-MPC-FHE-TEE a real creature? | Aztec Blog, https://aztec.network/blog/is-zk-mpc-fhe-tee-a-real-creature
59. [PDF] Efficiently Verifiable Computation on Encrypted Data - Semantic Scholar, https://www.semanticscholar.org/paper/Efficiently-Verifiable-Computation-on-Encrypted-Fiore-Gennaro/42389207a73223b03f533e02e2524581cf3c2f00
60. Fully Homomorphic Encryption performance - math-lock.com, https://www.math-lock.com/benchmarks.html
61. Privacy-Preserving Machine Learning | Harvard Architecture …, https://vlsiarch.eecs.harvard.edu/privacy-preserving-machine-learning
62. Fully Homomorphic Encryption with Applications to Privacy-Preserving Machine Learning - Harvard DASH, https://dash.harvard.edu/bitstreams/d5e8fdf8-45a9-42a2-9da5-90ec280050c5/download
63. Privacy Preserving ML with Fully Homomorphic Encryption - YouTube, https://www.youtube.com/watch?v=g1Zlu63TP0Y
64. Homomorphic Encryption Use Cases - IEEE Digital Privacy, https://digitalprivacy.ieee.org/publications/topics/homomorphic-encryption-use-cases/
65. (PDF) Zero-Knowledge Proofs for Secure and Private Voting Systems, https://www.researchgate.net/publication/393056936_Zero-Knowledge_Proofs_for_Secure_and_Private_Voting_Systems
66. Creating a Verifiable Election - ElectionGuard, https://www.electionguard.vote/concepts/Verifiability/
67. Anonymous Voting using Zero-knowledge Proofs - Chinmay Sonar, https://chinmaysonar.github.io/Projects/bc-zk-report.pdf
68. RETRACTED: A Publicly Verifiable E-Voting System Based on Biometrics - MDPI, https://www.mdpi.com/2410-387X/7/4/62
69. www.aiu.edu, https://www.aiu.edu/innovative/secure-cloud-computation-using-homomorphic-encryption/#:~:text=Homomorphic%20encryption%20allows%20secure%20data,surveillance%2C%20and%20secure%20voting%20systems.
70. Secure Cloud Computation Using Homomorphic Encryption, https://www.aiu.edu/innovative/secure-cloud-computation-using-homomorphic-encryption/
71. Privacy Tech-Know blog: Computing while blindfolded – Lifting the veil on homomorphic encryption, https://www.priv.gc.ca/en/blog/20231024/
72. What are Zero-Knowledge Rollups (ZK Rollups)? - Coinbase, https://www.coinbase.com/learn/crypto-glossary/what-are-zero-knowledge-zk-rollups
73. What are ZK-Rollups? How Zero-Knowledge Rollup Proofs work - MoonPay, https://www.moonpay.com/learn/blockchain/what-are-zk-rollups
74. 동형암호, http://www.kdcnet.kr/upfile/2023/11/20231123082311-2902.pdf